package com.eddie.recursion;

public class MiGong {

    private static String[][] MAP;

    /**
     * 私有化构造器
     */
    private MiGong() {
    }

    /**
     * 初始化迷宫
     */
    public static MiGong init() {
        MAP = new String[8][7];

        // 左右围墙建立
        for (int i = 0; i < MAP.length; i++) {
            buildWall(i, 0);
            buildWall(i, 6);
        }

        // 上下围墙建立
        for (int i = 0; i < MAP[0].length; i++) {
            buildWall(0, i);
            buildWall(7, i);
        }

        // 建造其他围墙
        buildWall(2, 1);
        buildWall(2, 2);
        for (int i = 1; i < 4; i++) {
            buildWall(i, 4);
        }
        for (int i = 2; i < 5; i++) {
            buildWall(5, i);
        }
        buildWall(3, 2);

        // 初始化开始位置和起始位置
        MAP[1][1] = "起点";
        MAP[6][5] = "终点";
        return new MiGong();
    }

    /**
     * 在指定位置建造墙
     *
     * @param i 行号
     * @param j 列号
     */
    public static void buildWall(int i, int j) {
        MAP[i][j] = "墙";
    }

    /**
     * 用来显示地图
     */
    public void showMap() {
        for (int i = 0; i < 8; i++) {
            for (int j = 0; j < 7; j++) {
                System.out.print(MAP[i][j] + "\t");
            }
            System.out.println();
        }
    }

    /**
     * 给小球获得路径
     * i,j表示：(i, j)表示从地图的哪个位置开始出发，这里我们默认为起点位置(1, 1)
     * 如果小球能到达终点位置(6, 5)，则路径找到了
     * <p>
     * 约定：
     * 当地图的(i, j)点为null，表示该点还没有探索过；
     * 当为"墙"时，表示该点为墙；
     * 当为"路"时，表示该点可以走；
     * 当为"*"时，表示该点已经探索过了，但是走不通；
     * <p>
     * 定制策略：
     * 在有多条路可以选择时，按照 上、右、下、左 的优先顺序进行选择，如果该点走不通，再回溯
     *
     * @param i 行位置
     * @param j 列位置
     * @return 该点能否走通 ? true : false
     */
    public boolean setWay(int i, int j) {
        // TODO 如果终点变成"路"，则已经找到通路
        if ("路".equals(MAP[6][5])) {
            return true;
        }
        // TODO 程序执行到此说明还没有找到最终通路
        // TODO 如果当前点为null(即还没有走过)
        if (MAP[i][j] == null || "起点".equals(MAP[i][j]) || "终点".equals(MAP[i][j])) {
            // TODO 假定该点可以走通
            MAP[i][j] = "路";

            // TODO 按照指定的策略走
            // 如果向上走的通
            if (setWay(i - 1, j)) {
                return true;
            // 如果向右走的通
            } else if (setWay(i, j + 1)) {
                return true;
            } else if (setWay(i + 1, j)) { // 如果向下走的通
                return true;
            } else if (setWay(i, j - 1)) { // 如果向左走的通
                return true;
            }
            // 程序执行到此，即上右下左都走不通，该点是死路
            MAP[i][j] = "*";
            return false;
        }
        // TODO 程序执行到此，说明如果当前点要么为"*"，要么为"墙"，即此点走不通；要么是"路"，即此点已走，但是还不知道能否走通，所以也返回false
        return false;
    }

    public static void main(String[] args) {
        MiGong miGong = init();
        System.out.println("迷宫：");
        miGong.showMap();
        System.out.println("路线(按照上右下左的策略)：");
        miGong.setWay(1, 1); // 从(1, 1)开始
        miGong.showMap();
    }


}
